package com.gemini.main.leetcode;


import java.util.*;

/**
 * gemini
 * com.gemini.main.leetcode.TopKFrequentWords
 *
 * 做法是维护一个有序序列（用链表来维护），每个链表的节点的key是 counter，value是list of elements that has this counter，也用linked list串起来。 比如 a出现2次，b出现3次，c出现2次，d出现1次。那么这个链表就是：
 *
 * {3: [b]} --> {2: [a ->c]} --> {1: [d]}
 * 然后另外还需要一个hashmap，key是element，value是这个element在链表上的具体位置。
 * 因为每一次的操作都是 counter + 1和 counter - 1，那么每次你通过 hashmap 找到对应的element在数据结构中的位置，+1的话，就是往头移动一格，-1的话，就是往尾巴移动一格。总而言之复杂度都是 O(1)。当你需要找 Top K 的时候，也是 O(k)的时间 可以解决的。
 *
 * @author zhanghailin
 */
public class TopKFrequentWords {

    /* Construct a bucket list
       index 1 contains  the list of words that appear once
       index 2 contains  the list of words that appear twice
       ...
       each list is actually a priority queue that sorts element by alphabetical order
       iterate bucket list from the larger index to smaller index, take k elements as answers
   */
    public List<String> topKFrequent(String[] words, int k) {
        List<String> ret = new ArrayList<>();
        List<PriorityQueue<String>> bucket_list = new ArrayList<>();
        for (int i = 0; i < words.length; i++) bucket_list.add(null);

        // map 存放的是单词在list中的index
        Map<String, Integer> map = new HashMap<>();

        for (String w : words) {
            Integer freq = map.get(w);
            if (freq == null) map.put(w, 1);
            else map.put(w, freq + 1);
        }

        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            String key = entry.getKey();// 单词
            int val = entry.getValue();// 单词出现的次数

            PriorityQueue<String> priorityQueue = bucket_list.get(val - 1);
            if (priorityQueue == null) {
                bucket_list.set(val - 1, new PriorityQueue<>());
                priorityQueue = bucket_list.get(val - 1);
            }
            priorityQueue.add(key);
        }

        for(int i = bucket_list.size() - 1; i >= 0; i--) {
            PriorityQueue<String> pq = bucket_list.get(i);
            if(pq == null) continue;
            while(pq.size() > 0 && k > 0) {
                ret.add(pq.poll());
                k--;
            }
        }

        return ret;
    }

    /**
     * PriorityQueue（优先队列），一个基于优先级堆的无界优先级队列
     * 实际上是一个堆（不指定Comparator时默认为最小堆），通过传入自定义的Comparator函数可以实现大顶堆。
     * 维护一个k的小顶堆 它将频率最小的候选项放在堆的顶部。最后，我们从堆中弹出最多 k 次，并反转结果，就可以得到前 k 个高频单词。
     * @param words
     * @param k
     * @return
     */
    public List<String> topKFrequentSolveWithHeap(String[] words, int k) {
        Map<String, Integer> count = new HashMap<>();
        for (String word: words) {
            count.put(word, count.getOrDefault(word, 0) + 1);
        }
        PriorityQueue<String> heap = new PriorityQueue<String>(
                (w1, w2) -> count.get(w1).equals(count.get(w2)) ?
                        w2.compareTo(w1) : count.get(w1) - count.get(w2) );

        for (String word: count.keySet()) {
            heap.offer(word);
            if (heap.size() > k) heap.poll();
        }

        List<String> ans = new ArrayList<>();
        while (!heap.isEmpty()) ans.add(heap.poll());
        Collections.reverse(ans);
        return ans;
    }



}
